# 接雨水


class Solution:
    def trap(self, height):
        n = len(height)

        prx =  [0] * (n + 2)
        back = [0] * (n + 2)
        
        for i, c in enumerate(height):
            prx[i + 1] = max(c, prx[i])
            back[-2 - i] = max(height[-1 - i], back[-1 - i])

        ans = 0
        # print(prx)
        # print(back)
        for i in range(1, n + 1):
            ans += min(prx[i], back[i]) - height[i - 1]

        return ans



if __name__ == "__main__":

    heihgt = [0,1,0,2,1,0,1,3,2,1,2,1]
    sol = Solution()
    res = sol.trap(heihgt)
    print(res)  









